grid1d

One-dimensional grids and interval partitions with mathematical rigor and performance optimization.

grid1d is a comprehensive Rust library for representing and manipulating one-dimensional grids, interval partitions and interval arithmetic with strong mathematical foundations, type safety, and performance optimizations. Designed for numerical computations, finite element methods, adaptive mesh refinement, and scientific computing applications requiring robust 1D spatial discretizations.

🎯 Key Features

Mathematical Correctness First

Type-safe intervals: Different interval types ([a,b], (a,b), etc.) encode boundary semantics at compile time
Domain validation: Runtime checks ensure grids completely partition their specified domains
Proper boundary handling: Open/closed boundary semantics correctly preserved in all operations
Generic scalar support: Works with any scalar type implementing num_valid::RealScalar

Multiple Floating-Point Backends

grid1d leverages the num-valid library to provide multiple numerical backends with different precision and performance characteristics:

Backend	Scalar Type	Precision	Performance	Best For
Native	`f64`	53 bits	⚡⚡⚡ Maximum	Production simulations, real-time
Native Validated (Debug)	`RealNative64StrictFiniteInDebug`	53 bits	⚡⚡⚡ Same as `f64`	Recommended for most applications
Native Validated	`RealNative64StrictFinite`	53 bits	⚡⚡ Small overhead	Safety-critical applications
Arbitrary Precision	`RealRugStrictFinite<N>`	N bits	⚡ Configurable	Scientific research, symbolic math

Performance Through Specialization

Uniform grids: O(1) point location with analytical formulas
Non-uniform grids: O(log n) binary search with optimized data structures
Memory efficiency: Zero-cost abstractions and cache-friendly memory layouts
SIMD-ready: Regular patterns enable vectorization optimizations

Advanced Grid Operations

Adaptive mesh refinement: Uniform and selective refinement with bidirectional mappings
Grid union: Combine grids from different physics for multi-physics simulations
Interval arithmetic: Complete set of interval operations with proper boundary handling
Type-safe scalars: Prevent common numerical bugs with validated scalar types

🚀 Quick Start

Prerequisites

This library requires Rust nightly for advanced language features:

# rust-toolchain.toml (automatically configured)
[toolchain]
channel = "nightly"

Why nightly is required:

Advanced error handling (#![feature(error_generic_member_access)]): Better debugging and error context
Future optimizations: Enables cutting-edge Rust developments for numerical computing

Installation

Add this to your Cargo.toml:

[dependencies]
grid1d = "0.1.0" # change to the latest versione

# For arbitrary precision arithmetic
grid1d = { version = "0.1.0", features = ["rug"] }  # change `version` to the latest available

Basic Usage

use grid1d::{
    Grid1D, IntervalPartition, HasCoords1D,
    intervals::IntervalClosed,
    scalars::{NumIntervals, IntervalId},
};
use sorted_vec::partial::SortedSet;

// Create uniform grid with equal spacing
let domain = IntervalClosed::new(0.0, 1.0);
let uniform_grid = Grid1D::uniform(domain.clone(), NumIntervals::try_new(4).unwrap());
assert_eq!(uniform_grid.coords().deref(), &[0.0, 0.25, 0.5, 0.75, 1.0]);

// Create non-uniform grid with custom spacing  
let coords = SortedSet::from_unsorted(vec![0.0, 0.1, 0.5, 0.9, 1.0]);
let non_uniform_grid = Grid1D::try_from_sorted(domain, coords).unwrap();

// Both grids implement the same IntervalPartition trait
assert_eq!(uniform_grid.num_intervals().as_ref(), &4);
assert_eq!(non_uniform_grid.num_intervals().as_ref(), &4);

// Efficient point location
let interval_id = uniform_grid.find_interval_id_of_point(&0.3);
let interval = uniform_grid.interval(&interval_id);

Working with Different Scalar Types

use grid1d::{Grid1D, intervals::IntervalClosed, scalars::NumIntervals};
use num_valid::{RealNative64StrictFiniteInDebug, RealNative64StrictFinite};
use try_create::TryNew;

// Performance-optimal with debug safety (recommended)
type OptimalReal = RealNative64StrictFiniteInDebug;
let optimal_grid = Grid1D::uniform(
    IntervalClosed::new(
        OptimalReal::try_new(0.0).unwrap(),
        OptimalReal::try_new(1.0).unwrap()
    ),
    NumIntervals::try_new(4).unwrap()
);

// Always validated for safety-critical applications
type SafeReal = RealNative64StrictFinite;
let safe_grid = Grid1D::uniform(
    IntervalClosed::new(
        SafeReal::try_new(0.0).unwrap(),
        SafeReal::try_new(1.0).unwrap()
    ),
    NumIntervals::try_new(4).unwrap()
);

Arbitrary Precision with Rug

For applications requiring arbitrary precision arithmetic:

// Add to Cargo.toml:
// grid1d = { version = "0.1.0", features = ["rug"] }

use grid1d::{Grid1D, intervals::IntervalClosed, scalars::NumIntervals};
use num_valid::RealRugStrictFinite;
use try_create::TryNew;

// 256-bit precision arithmetic
type HighPrecisionReal = RealRugStrictFinite<256>;

let high_precision_grid = Grid1D::uniform(
    IntervalClosed::new(
        HighPrecisionReal::try_new(0.0).unwrap(),
        HighPrecisionReal::try_new(1.0).unwrap()
    ),
    NumIntervals::try_new(4).unwrap()
);

// All grid operations work seamlessly with arbitrary precision
let hp_1 = HighPrecisionReal::try_new(1.0).unwrap();
let hp_3 = HighPrecisionReal::try_new(3.0).unwrap();
let point = hp_1 / hp_3; // 1. / 3.
let interval_id = high_precision_grid.find_interval_id_of_point(&point);

🔬 Advanced Features

Adaptive Mesh Refinement

use grid1d::{*, intervals::*, scalars::*};

let base_grid = Grid1D::uniform(IntervalClosed::new(0.0, 1.0), NumIntervals::try_new(4).unwrap());

// Uniform refinement: double resolution everywhere
let uniform_refinement = base_grid.refine_uniform(&PositiveNumPoints1D::try_new(1).unwrap());
assert_eq!(uniform_refinement.refined_grid().num_intervals().as_ref(), &8);

// Selective refinement: refine only specific intervals
let selective_plan = [
    (IntervalId::new(1), PositiveNumPoints1D::try_new(2).unwrap()), // 3 sub-intervals
    (IntervalId::new(3), PositiveNumPoints1D::try_new(1).unwrap()), // 2 sub-intervals
];
let selective_refinement = uniform_refinement.into_refined_grid().refine(&selective_plan);

Grid Union for Multi-Physics

use grid1d::{*, intervals::*, scalars::*};
use sorted_vec::partial::SortedSet;

let domain = IntervalClosed::new(0.0, 2.0);

// Physics A: coarse global grid
let grid_a = Grid1D::uniform(domain.clone(), NumIntervals::try_new(4).unwrap());

// Physics B: fine local grid
let coords_b = SortedSet::from_unsorted(vec![0.0, 0.3, 0.7, 1.1, 1.4, 2.0]);
let grid_b = Grid1D::try_from_sorted(domain, coords_b).unwrap();

// Create unified grid preserving mappings to both original grids
let union = Grid1DUnion::try_new(&grid_a, &grid_b).unwrap();
println!("Unified grid has {} intervals", union.num_refined_intervals().as_ref());

// Map data between grids
for (refined_id, a_id, b_id) in union.iter_interval_mappings() {
    println!("Unified interval {} maps to A[{}] and B[{}]",
             refined_id.as_ref(), a_id.as_ref(), b_id.as_ref());
}

Working with Different Interval Types

use grid1d::intervals::*;

let closed = IntervalClosed::new(0.0, 1.0);         // [0, 1]
let open = IntervalOpen::new(0.0, 1.0);             // (0, 1)
let half_open = IntervalLowerClosedUpperOpen::new(0.0, 1.0); // [0, 1)
let unbounded = IntervalLowerClosedUpperUnbounded::new(0.0); // [0, +∞)

// All implement IntervalTrait for generic operations
assert!(closed.contains_point(&0.0));
assert!(!open.contains_point(&0.0));

🏗️ Core Concepts

Grid Types and Performance Characteristics

Grid Type	Point Location	Memory	Best For
`Grid1DUniform`	O(1) analytical	O(n)	Equal spacing, maximum performance
`Grid1DNonUniform`	O(log n) binary search	O(n)	Adaptive spacing, complex features
`Grid1DUnion`	O(log n) on unified grid	O(n+m)	Multi-physics, grid combination

Interval Partition Types

The library correctly handles different interval boundary semantics:

Closed intervals [a,b]: Include both endpoints
Open intervals (a,b): Exclude both endpoints
Semi-open intervals: [a,b) or (a,b] - include one endpoint
Automatic sub-interval construction: Preserves domain semantics in partitions

Mathematical Properties and Guarantees

Every grid maintains these invariants:

Complete domain coverage: ⋃ intervals = domain (exact reconstruction)
Non-overlapping intervals: Intervals are disjoint except at boundaries
Unique point location: Every domain point belongs to exactly one interval
Boundary consistency: First/last coordinates match domain bounds exactly
Sorted coordinates: Points are in strict ascending order

📖 Examples

Finite Difference Methods

use grid1d::{*, intervals::*, scalars::*};

let grid = Grid1D::uniform(IntervalClosed::new(0.0, 1.0), NumIntervals::try_new(100).unwrap());
let dx = grid.coords()[1] - grid.coords()[0];

// Apply finite difference stencils
for i in 1..grid.coords().len()-1 {
    let d2u_dx2 = (solution[i-1] - 2.0*solution[i] + solution[i+1]) / (dx * dx);
    // Time stepping logic...
}

Spectral Methods

use grid1d::{*, intervals::*};

// Periodic domain for Fourier spectral methods
let domain = IntervalLowerClosedUpperOpen::new(0.0, 2.0 * std::f64::consts::PI);
let grid = Grid1D::uniform(domain, NumIntervals::try_new(256).unwrap());

// Perfect for FFT algorithms
let dx = grid.coords()[1] - grid.coords()[0];
assert!((dx - 2.0 * std::f64::consts::PI / 256.0).abs() < 1e-15);

Boundary Layer Refinement

use grid1d::{*, intervals::*, scalars::*};
use sorted_vec::partial::SortedSet;

// Create boundary layer mesh with fine spacing near walls
fn create_boundary_layer_mesh(domain_length: f64, boundary_thickness: f64)
    -> Grid1D<IntervalClosed<f64>>
{
    let mut points = vec![0.0];
    
    // Fine spacing in boundary layer
    for i in 1..=20 {
        let eta = (i as f64) / 20.0;
        let y = boundary_thickness * (eta * eta); // Quadratic clustering
        points.push(y);
    }
    
    // Coarse spacing in outer region
    for i in 1..=10 {
        let y = boundary_thickness + (domain_length - boundary_thickness) * (i as f64) / 10.0;
        points.push(y);
    }
    
    Grid1D::try_from_sorted(
        IntervalClosed::new(0.0, domain_length),
        SortedSet::from_unsorted(points)
    ).unwrap()
}

let cfd_grid = create_boundary_layer_mesh(1.0, 0.1);
println!("CFD grid: {} intervals", cfd_grid.num_intervals().as_ref());

🛠️ Development

Building

# Standard build (uses nightly automatically)
cargo build

# With arbitrary precision support
cargo build --features=rug

# Run tests
cargo test

# Run tests with arbitrary precision
cargo test --features=rug

# Generate documentation
cargo doc --open

Requirements

Rust: Nightly toolchain (specified in rust-toolchain.toml)

Core Dependencies

[num-valid]: Validated scalar arithmetic
[sorted-vec]: Efficient sorted container implementation
[serde]: Serialization support for grid structures
[nutype]: Type-safe wrapper generation
[derive-more]: Ergonomic derive macros
[getset]: Automatic getter generation

Optional Dependencies

[rug]: Arbitrary precision arithmetic via the rug library
- Enable with --features=rug
- Provides num_valid::RealRugStrictFinite<N> types for N-bit precision

🧪 Testing

The library includes comprehensive test suites:

# Run all tests
cargo test

# Run tests with arbitrary precision
cargo test --features=rug

# Run property-based tests
cargo test --test property_tests

# Run benchmarks
cargo bench

Test Coverage

Unit tests: Core functionality for all grid types
Integration tests: Cross-module interactions
Property-based tests: Mathematical invariants and edge cases
Benchmarks: Performance regression detection
Documentation tests: All code examples in docs are tested

Development Setup

Clone the repository:

git clone git@gitlab.com:max.martinelli/grid1d.git
cd grid1d

Ensure you have the required dependencies:
- Rust nightly toolchain
Run the test suite:
```
cargo test --all-features
```

Check formatting and linting:

cargo fmt --check
cargo clippy --all-features

Contribution Guidelines

Mathematical correctness: All changes must preserve mathematical guarantees
Performance: Performance-critical paths must maintain or improve benchmarks
Documentation: All public APIs must be thoroughly documented with examples
Testing: New features require comprehensive test coverage
Type safety: Leverage Rust's type system for compile-time correctness

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.

🔗 Related Projects

[num-valid]: Generic validated scalar arithmetic
[ndarray]: N-dimensional arrays for Rust
[nalgebra]: Linear algebra library
[faer]: High-performance linear algebra
[polars]: Fast DataFrame library

📚 Documentation

For comprehensive API documentation, mathematical foundations, and advanced usage patterns:

API Documentation: Complete API reference
Mathematical Foundations: Theoretical background
Performance Guide: Optimization strategies
Examples: Practical usage examples

🎯 Use Cases

grid1d is designed for:

Scientific Computing

Computational Fluid Dynamics: Boundary layer meshes, shock capturing
Finite Element Analysis: Adaptive mesh refinement, domain decomposition
Spectral Methods: Fourier transforms, Chebyshev polynomials
Numerical Integration: Quadrature rules, adaptive integration

Engineering Applications

Heat Transfer: Non-uniform grids for boundary layers
Structural Analysis: Stress concentration regions
Signal Processing: Non-uniform sampling, filter design
Control Systems: State-space discretization

Data Science

Time Series: Irregular time grids, event-driven sampling
Interpolation: Scattered data, adaptive sampling
Numerical Methods: Root finding, optimization
Machine Learning: Feature engineering, data preprocessing

License

Licensed under either of

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

License Notice for Optional Feature Dependencies (LGPL-3.0 Compliance)

If you enable the rug feature, this project will depend on the rug library, which is licensed under the LGPL-3.0 license. Activating this feature may introduce LGPL-3.0 requirements to your project. Please review the terms of the LGPL-3.0 license to ensure compliance.

grid1d 0.1.0