scirs2_interpolate/
doc_enhancements.rs

1//! Documentation enhancements and complexity analysis for interpolation methods
2//!
3//! This module provides comprehensive documentation utilities including:
4//! - Computational complexity analysis
5//! - Memory complexity analysis  
6//! - Performance characteristics
7//! - Usage recommendations
8//! - Method comparison guides
9
10use std::fmt::{Display, Formatter, Result as FmtResult};
11
12/// Computational complexity classification
13#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
14pub enum ComputationalComplexity {
15    /// O(1) - Constant time
16    Constant,
17    /// O(log n) - Logarithmic time
18    Logarithmic,
19    /// O(n) - Linear time
20    Linear,
21    /// O(n log n) - Linearithmic time
22    Linearithmic,
23    /// O(n²) - Quadratic time
24    Quadratic,
25    /// O(n³) - Cubic time
26    Cubic,
27    /// O(2^n) - Exponential time
28    Exponential,
29}
30
31impl Display for ComputationalComplexity {
32    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
33        match self {
34            ComputationalComplexity::Constant => write!(f, "O(1)"),
35            ComputationalComplexity::Logarithmic => write!(f, "O(log n)"),
36            ComputationalComplexity::Linear => write!(f, "O(n)"),
37            ComputationalComplexity::Linearithmic => write!(f, "O(n log n)"),
38            ComputationalComplexity::Quadratic => write!(f, "O(n²)"),
39            ComputationalComplexity::Cubic => write!(f, "O(n³)"),
40            ComputationalComplexity::Exponential => write!(f, "O(2^n)"),
41        }
42    }
43}
44
45/// Memory complexity classification
46#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
47pub enum MemoryComplexity {
48    /// O(1) - Constant space
49    Constant,
50    /// O(n) - Linear space
51    Linear,
52    /// O(n²) - Quadratic space
53    Quadratic,
54    /// O(n³) - Cubic space
55    Cubic,
56}
57
58impl Display for MemoryComplexity {
59    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
60        match self {
61            MemoryComplexity::Constant => write!(f, "O(1)"),
62            MemoryComplexity::Linear => write!(f, "O(n)"),
63            MemoryComplexity::Quadratic => write!(f, "O(n²)"),
64            MemoryComplexity::Cubic => write!(f, "O(n³)"),
65        }
66    }
67}
68
69/// Performance characteristics of an interpolation method
70#[derive(Debug, Clone)]
71pub struct PerformanceCharacteristics {
72    /// Time complexity for construction/fitting
73    pub construction_complexity: ComputationalComplexity,
74    /// Time complexity for evaluation at a single point
75    pub evaluation_complexity: ComputationalComplexity,
76    /// Time complexity for batch evaluation at m points
77    pub batch_evaluation_complexity: ComputationalComplexity,
78    /// Memory complexity
79    pub memory_complexity: MemoryComplexity,
80    /// Whether the method is suitable for real-time applications
81    pub real_time_suitable: bool,
82    /// Whether the method supports parallel evaluation
83    pub parallel_evaluation: bool,
84    /// Whether the method is numerically stable
85    pub numerically_stable: bool,
86    /// Typical accuracy level (relative error)
87    pub typical_accuracy: f64,
88}
89
90/// Usage recommendation for interpolation methods
91#[derive(Debug, Clone)]
92pub struct UsageRecommendation {
93    /// Recommended data size range
94    pub recommended_data_size: (usize, Option<usize>),
95    /// Best use cases
96    pub best_use_cases: Vec<String>,
97    /// When to avoid this method
98    pub avoid_when: Vec<String>,
99    /// Alternative methods to consider
100    pub alternatives: Vec<String>,
101    /// Configuration tips
102    pub configuration_tips: Vec<String>,
103}
104
105/// Comprehensive method documentation
106#[derive(Debug, Clone)]
107pub struct MethodDocumentation {
108    /// Method name
109    pub method_name: String,
110    /// Brief description
111    pub description: String,
112    /// Performance characteristics
113    pub performance: PerformanceCharacteristics,
114    /// Usage recommendations
115    pub usage: UsageRecommendation,
116    /// Mathematical background
117    pub mathematical_background: String,
118    /// Implementation notes
119    pub implementation_notes: Vec<String>,
120    /// References to papers/algorithms
121    pub references: Vec<String>,
122}
123
124/// Generate documentation for common interpolation methods
125#[allow(dead_code)]
126pub fn get_method_documentation(method_name: &str) -> Option<MethodDocumentation> {
127    match method_name {
128        "linear" => Some(linear_interpolation_docs()),
129        "cubic" => Some(cubic_interpolation_docs()),
130        "pchip" => Some(pchip_interpolation_docs()),
131        "bspline" => Some(bspline_interpolation_docs()),
132        "rbf" => Some(rbf_interpolation_docs()),
133        "kriging" => Some(kriging_interpolation_docs()),
134        "akima" => Some(akima_interpolation_docs()),
135        "hermite" => Some(hermite_interpolation_docs()),
136        _ => None,
137    }
138}
139
140/// Linear interpolation documentation
141#[allow(dead_code)]
142fn linear_interpolation_docs() -> MethodDocumentation {
143    MethodDocumentation {
144        method_name: "Linear Interpolation".to_string(),
145        description: "Piecewise linear interpolation connecting adjacent data points with straight lines".to_string(),
146        performance: PerformanceCharacteristics {
147            construction_complexity: ComputationalComplexity::Linear,
148            evaluation_complexity: ComputationalComplexity::Logarithmic,
149            batch_evaluation_complexity: ComputationalComplexity::Linearithmic,
150            memory_complexity: MemoryComplexity::Linear,
151            real_time_suitable: true,
152            parallel_evaluation: true,
153            numerically_stable: true,
154            typical_accuracy: 1e-2,
155        },
156        usage: UsageRecommendation {
157            recommended_data_size: (2, Some(1_000_000)),
158            best_use_cases: vec![
159                "Real-time applications".to_string(),
160                "Large datasets".to_string(),
161                "When simplicity is required".to_string(),
162                "Preserving monotonicity".to_string(),
163            ],
164            avoid_when: vec![
165                "High accuracy requirements".to_string(),
166                "Smooth derivatives needed".to_string(),
167                "Data has high curvature".to_string(),
168            ],
169            alternatives: vec![
170                "Cubic splines for smoothness".to_string(),
171                "PCHIP for shape preservation".to_string(),
172                "Akima for outlier robustness".to_string(),
173            ],
174            configuration_tips: vec![
175                "Ensure input data is sorted".to_string(),
176                "Consider preprocessing for noise reduction".to_string(),
177            ],
178        },
179        mathematical_background: "Given points (x₀,y₀)...(xₙ,yₙ), interpolates using f(x) = y₀ + (y₁-y₀)*(x-x₀)/(x₁-x₀) for x ∈ [x₀,x₁]".to_string(),
180        implementation_notes: vec![
181            "Uses binary search for interval location".to_string(),
182            "Supports extrapolation with constant or linear modes".to_string(),
183            "Vectorized implementation available for batch evaluation".to_string(),
184        ],
185        references: vec![
186            "Burden, R.L., Faires, J.D. (2010). Numerical Analysis, 9th Edition".to_string(),
187        ],
188    }
189}
190
191/// Cubic spline interpolation documentation
192#[allow(dead_code)]
193fn cubic_interpolation_docs() -> MethodDocumentation {
194    MethodDocumentation {
195        method_name: "Cubic Spline Interpolation".to_string(),
196        description: "Smooth piecewise cubic polynomial interpolation with continuous first and second derivatives".to_string(),
197        performance: PerformanceCharacteristics {
198            construction_complexity: ComputationalComplexity::Linear,
199            evaluation_complexity: ComputationalComplexity::Logarithmic,
200            batch_evaluation_complexity: ComputationalComplexity::Linearithmic,
201            memory_complexity: MemoryComplexity::Linear,
202            real_time_suitable: false,
203            parallel_evaluation: true,
204            numerically_stable: true,
205            typical_accuracy: 1e-6,
206        },
207        usage: UsageRecommendation {
208            recommended_data_size: (4, Some(100_000)),
209            best_use_cases: vec![
210                "Smooth curve fitting".to_string(),
211                "Derivative estimation".to_string(),
212                "Integration applications".to_string(),
213                "Animation and graphics".to_string(),
214            ],
215            avoid_when: vec![
216                "Real-time constraints".to_string(),
217                "Non-smooth underlying functions".to_string(),
218                "Presence of outliers".to_string(),
219            ],
220            alternatives: vec![
221                "Linear for speed".to_string(),
222                "PCHIP for shape preservation".to_string(),
223                "B-splines for more control".to_string(),
224            ],
225            configuration_tips: vec![
226                "Choose appropriate boundary conditions".to_string(),
227                "Natural boundaries for unknown derivatives".to_string(),
228                "Clamped boundaries when derivatives are known".to_string(),
229            ],
230        },
231        mathematical_background: "Constructs cubic polynomials S(x) = aᵢ + bᵢ(x-xᵢ) + cᵢ(x-xᵢ)² + dᵢ(x-xᵢ)³ with C² continuity".to_string(),
232        implementation_notes: vec![
233            "Solves tridiagonal system for coefficients".to_string(),
234            "Supports multiple boundary conditions".to_string(),
235            "Provides derivative and integral methods".to_string(),
236        ],
237        references: vec![
238            "de Boor, C. (1978). A Practical Guide to Splines".to_string(),
239            "Burden, R.L., Faires, J.D. (2010). Numerical Analysis, 9th Edition".to_string(),
240        ],
241    }
242}
243
244/// PCHIP interpolation documentation
245#[allow(dead_code)]
246fn pchip_interpolation_docs() -> MethodDocumentation {
247    MethodDocumentation {
248        method_name: "PCHIP (Piecewise Cubic Hermite Interpolating Polynomial)".to_string(),
249        description: "Shape-preserving cubic interpolation that maintains monotonicity and avoids overshooting".to_string(),
250        performance: PerformanceCharacteristics {
251            construction_complexity: ComputationalComplexity::Linear,
252            evaluation_complexity: ComputationalComplexity::Logarithmic,
253            batch_evaluation_complexity: ComputationalComplexity::Linearithmic,
254            memory_complexity: MemoryComplexity::Linear,
255            real_time_suitable: false,
256            parallel_evaluation: true,
257            numerically_stable: true,
258            typical_accuracy: 1e-4,
259        },
260        usage: UsageRecommendation {
261            recommended_data_size: (3, Some(50_000)),
262            best_use_cases: vec![
263                "Monotonic data".to_string(),
264                "Avoiding oscillations".to_string(),
265                "Financial data interpolation".to_string(),
266                "Physical measurements".to_string(),
267            ],
268            avoid_when: vec![
269                "High-frequency oscillations needed".to_string(),
270                "Maximum smoothness required".to_string(),
271            ],
272            alternatives: vec![
273                "Cubic splines for smoothness".to_string(),
274                "Akima for outlier robustness".to_string(),
275                "Linear for simplicity".to_string(),
276            ],
277            configuration_tips: vec![
278                "Works best with monotonic data".to_string(),
279                "No additional parameters needed".to_string(),
280            ],
281        },
282        mathematical_background: "Uses Fritsch-Carlson method to compute derivatives that preserve shape, then builds cubic Hermite polynomials".to_string(),
283        implementation_notes: vec![
284            "Automatically computes shape-preserving derivatives".to_string(),
285            "Handles flat regions gracefully".to_string(),
286            "No oscillations near extrema".to_string(),
287        ],
288        references: vec![
289            "Fritsch, F.N., Carlson, R.E. (1980). Monotone Piecewise Cubic Interpolation".to_string(),
290        ],
291    }
292}
293
294/// B-spline interpolation documentation
295#[allow(dead_code)]
296fn bspline_interpolation_docs() -> MethodDocumentation {
297    MethodDocumentation {
298        method_name: "B-spline Interpolation".to_string(),
299        description: "Flexible spline interpolation using basis functions with adjustable degree and knot placement".to_string(),
300        performance: PerformanceCharacteristics {
301            construction_complexity: ComputationalComplexity::Linear,
302            evaluation_complexity: ComputationalComplexity::Constant,
303            batch_evaluation_complexity: ComputationalComplexity::Linear,
304            memory_complexity: MemoryComplexity::Linear,
305            real_time_suitable: true,
306            parallel_evaluation: true,
307            numerically_stable: true,
308            typical_accuracy: 1e-8,
309        },
310        usage: UsageRecommendation {
311            recommended_data_size: (5, Some(1_000_000)),
312            best_use_cases: vec![
313                "CAD/CAM applications".to_string(),
314                "Computer graphics".to_string(),
315                "Signal processing".to_string(),
316                "Large datasets".to_string(),
317            ],
318            avoid_when: vec![
319                "Simple linear relationships".to_string(),
320                "When knot placement is unclear".to_string(),
321            ],
322            alternatives: vec![
323                "Cubic splines for automatic knot placement".to_string(),
324                "NURBS for rational curves".to_string(),
325            ],
326            configuration_tips: vec![
327                "Choose degree based on smoothness needs".to_string(),
328                "Use uniform knots for regular data".to_string(),
329                "Consider least-squares fitting for noisy data".to_string(),
330            ],
331        },
332        mathematical_background: "Constructs splines as linear combinations of B-spline basis functions: S(x) = Σ cᵢ Nᵢ,ₖ(x)".to_string(),
333        implementation_notes: vec![
334            "Uses de Boor's algorithm for evaluation".to_string(),
335            "Supports arbitrary degree and knot vectors".to_string(),
336            "Efficient derivative computation".to_string(),
337        ],
338        references: vec![
339            "de Boor, C. (1978). A Practical Guide to Splines".to_string(),
340            "Piegl, L., Tiller, W. (1997). The NURBS Book".to_string(),
341        ],
342    }
343}
344
345/// RBF interpolation documentation
346#[allow(dead_code)]
347fn rbf_interpolation_docs() -> MethodDocumentation {
348    MethodDocumentation {
349        method_name: "Radial Basis Function (RBF) Interpolation".to_string(),
350        description: "Meshfree interpolation method using radially symmetric basis functions centered at data points".to_string(),
351        performance: PerformanceCharacteristics {
352            construction_complexity: ComputationalComplexity::Cubic,
353            evaluation_complexity: ComputationalComplexity::Linear,
354            batch_evaluation_complexity: ComputationalComplexity::Quadratic,
355            memory_complexity: MemoryComplexity::Quadratic,
356            real_time_suitable: false,
357            parallel_evaluation: true,
358            numerically_stable: false, // Can be ill-conditioned
359            typical_accuracy: 1e-10,
360        },
361        usage: UsageRecommendation {
362            recommended_data_size: (5, Some(5_000)),
363            best_use_cases: vec![
364                "Scattered data interpolation".to_string(),
365                "Multivariate interpolation".to_string(),
366                "Irregular grids".to_string(),
367                "High accuracy requirements".to_string(),
368            ],
369            avoid_when: vec![
370                "Large datasets (>10,000 points)".to_string(),
371                "Real-time applications".to_string(),
372                "Ill-conditioned data".to_string(),
373            ],
374            alternatives: vec![
375                "Fast RBF for large datasets".to_string(),
376                "Kriging for uncertainty quantification".to_string(),
377                "Moving least squares for local approximation".to_string(),
378            ],
379            configuration_tips: vec![
380                "Choose shape parameter carefully".to_string(),
381                "Use regularization for stability".to_string(),
382                "Consider conditioning for large datasets".to_string(),
383            ],
384        },
385        mathematical_background: "Approximates f(x) = Σ λᵢ φ(||x - xᵢ||) where φ is the RBF and λᵢ are coefficients".to_string(),
386        implementation_notes: vec![
387            "Solves dense linear system Aλ = f".to_string(),
388            "Multiple kernel options available".to_string(),
389            "Supports polynomial augmentation".to_string(),
390        ],
391        references: vec![
392            "Buhmann, M.D. (2003). Radial Basis Functions: Theory and Implementations".to_string(),
393            "Fasshauer, G.E. (2007). Meshfree Approximation Methods with MATLAB".to_string(),
394        ],
395    }
396}
397
398/// Kriging interpolation documentation
399#[allow(dead_code)]
400fn kriging_interpolation_docs() -> MethodDocumentation {
401    MethodDocumentation {
402        method_name: "Kriging (Gaussian Process Regression)".to_string(),
403        description: "Statistical interpolation method that provides uncertainty estimates along with predictions".to_string(),
404        performance: PerformanceCharacteristics {
405            construction_complexity: ComputationalComplexity::Cubic,
406            evaluation_complexity: ComputationalComplexity::Linear,
407            batch_evaluation_complexity: ComputationalComplexity::Quadratic,
408            memory_complexity: MemoryComplexity::Quadratic,
409            real_time_suitable: false,
410            parallel_evaluation: true,
411            numerically_stable: false, // Can be ill-conditioned
412            typical_accuracy: 1e-8,
413        },
414        usage: UsageRecommendation {
415            recommended_data_size: (5, Some(3_000)),
416            best_use_cases: vec![
417                "Uncertainty quantification".to_string(),
418                "Noisy data".to_string(),
419                "Spatial statistics".to_string(),
420                "Optimization (Bayesian)".to_string(),
421            ],
422            avoid_when: vec![
423                "Large datasets".to_string(),
424                "Deterministic data".to_string(),
425                "Real-time requirements".to_string(),
426            ],
427            alternatives: vec![
428                "Fast kriging for larger datasets".to_string(),
429                "RBF for deterministic interpolation".to_string(),
430                "Enhanced kriging for better conditioning".to_string(),
431            ],
432            configuration_tips: vec![
433                "Choose covariance function based on data characteristics".to_string(),
434                "Use nugget effect for noisy data".to_string(),
435                "Consider anisotropy for directional data".to_string(),
436            ],
437        },
438        mathematical_background: "Models data as realization of Gaussian process: f(x) ~ GP(μ(x), k(x,x')) with covariance function k".to_string(),
439        implementation_notes: vec![
440            "Provides prediction variance".to_string(),
441            "Multiple covariance functions supported".to_string(),
442            "Can handle trend functions".to_string(),
443        ],
444        references: vec![
445            "Cressie, N. (1993). Statistics for Spatial Data".to_string(),
446            "Rasmussen, C.E., Williams, C.K.I. (2006). Gaussian Processes for Machine Learning".to_string(),
447        ],
448    }
449}
450
451/// Akima interpolation documentation
452#[allow(dead_code)]
453fn akima_interpolation_docs() -> MethodDocumentation {
454    MethodDocumentation {
455        method_name: "Akima Spline Interpolation".to_string(),
456        description: "Robust piecewise cubic interpolation that reduces oscillations and is less sensitive to outliers".to_string(),
457        performance: PerformanceCharacteristics {
458            construction_complexity: ComputationalComplexity::Linear,
459            evaluation_complexity: ComputationalComplexity::Logarithmic,
460            batch_evaluation_complexity: ComputationalComplexity::Linearithmic,
461            memory_complexity: MemoryComplexity::Linear,
462            real_time_suitable: false,
463            parallel_evaluation: true,
464            numerically_stable: true,
465            typical_accuracy: 1e-5,
466        },
467        usage: UsageRecommendation {
468            recommended_data_size: (5, Some(50_000)),
469            best_use_cases: vec![
470                "Data with outliers".to_string(),
471                "Irregular spacing".to_string(),
472                "Avoiding oscillations".to_string(),
473                "Geophysical data".to_string(),
474            ],
475            avoid_when: vec![
476                "Maximum smoothness required".to_string(),
477                "High-frequency content".to_string(),
478            ],
479            alternatives: vec![
480                "Cubic splines for smoothness".to_string(),
481                "PCHIP for monotonicity".to_string(),
482                "Robust splines for heavy outliers".to_string(),
483            ],
484            configuration_tips: vec![
485                "No parameters to tune".to_string(),
486                "Works well with default settings".to_string(),
487            ],
488        },
489        mathematical_background: "Uses local polynomial fitting with weighted averages to estimate derivatives, reducing oscillations".to_string(),
490        implementation_notes: vec![
491            "Estimates derivatives using Akima's method".to_string(),
492            "Less sensitive to isolated outliers".to_string(),
493            "Maintains local shape characteristics".to_string(),
494        ],
495        references: vec![
496            "Akima, H. (1970). A New Method of Interpolation and Smooth Curve Fitting".to_string(),
497        ],
498    }
499}
500
501/// Hermite interpolation documentation
502#[allow(dead_code)]
503fn hermite_interpolation_docs() -> MethodDocumentation {
504    MethodDocumentation {
505        method_name: "Hermite Interpolation".to_string(),
506        description: "Polynomial interpolation that matches both function values and derivatives at specified points".to_string(),
507        performance: PerformanceCharacteristics {
508            construction_complexity: ComputationalComplexity::Quadratic,
509            evaluation_complexity: ComputationalComplexity::Linear,
510            batch_evaluation_complexity: ComputationalComplexity::Quadratic,
511            memory_complexity: MemoryComplexity::Quadratic,
512            real_time_suitable: false,
513            parallel_evaluation: true,
514            numerically_stable: false, // High-degree polynomials
515            typical_accuracy: 1e-12,
516        },
517        usage: UsageRecommendation {
518            recommended_data_size: (2, Some(1_000)),
519            best_use_cases: vec![
520                "Known derivatives".to_string(),
521                "Boundary value problems".to_string(),
522                "Animation interpolation".to_string(),
523                "Small datasets".to_string(),
524            ],
525            avoid_when: vec![
526                "Large datasets".to_string(),
527                "Unknown derivatives".to_string(),
528                "Risk of oscillations".to_string(),
529            ],
530            alternatives: vec![
531                "Cubic splines for large datasets".to_string(),
532                "PCHIP for automatic derivatives".to_string(),
533                "B-splines for better conditioning".to_string(),
534            ],
535            configuration_tips: vec![
536                "Provide accurate derivatives".to_string(),
537                "Consider piecewise approach for large intervals".to_string(),
538            ],
539        },
540        mathematical_background: "Constructs polynomial of degree 2n-1 to interpolate n points with specified derivatives".to_string(),
541        implementation_notes: vec![
542            "Supports cubic and quintic variants".to_string(),
543            "Multiple derivative specification methods".to_string(),
544            "Direct polynomial evaluation".to_string(),
545        ],
546        references: vec![
547            "Burden, R.L., Faires, J.D. (2010). Numerical Analysis, 9th Edition".to_string(),
548        ],
549    }
550}
551
552/// Print comprehensive method comparison
553#[allow(dead_code)]
554pub fn print_method_comparison() {
555    let methods = [
556        "linear", "cubic", "pchip", "bspline", "rbf", "kriging", "akima", "hermite",
557    ];
558
559    println!("# Interpolation Methods Comparison\n");
560
561    for method in &methods {
562        if let Some(doc) = get_method_documentation(method) {
563            println!("## {}\n", doc.method_name);
564            println!("{}\n", doc.description);
565
566            println!("**Performance Characteristics:**");
567            println!(
568                "- Construction: {}",
569                doc.performance.construction_complexity
570            );
571            println!("- Evaluation: {}", doc.performance.evaluation_complexity);
572            println!("- Memory: {}", doc.performance.memory_complexity);
573            println!(
574                "- Real-time suitable: {}",
575                doc.performance.real_time_suitable
576            );
577            println!(
578                "- Typical accuracy: {:.0e}\n",
579                doc.performance.typical_accuracy
580            );
581
582            println!("**Best for:** {}\n", doc.usage.best_use_cases.join(", "));
583            println!("**Avoid when:** {}\n", doc.usage.avoid_when.join(", "));
584            println!("---\n");
585        }
586    }
587}
588
589#[cfg(test)]
590mod tests {
591    use super::*;
592
593    #[test]
594    fn test_complexity_display() {
595        assert_eq!(ComputationalComplexity::Linear.to_string(), "O(n)");
596        assert_eq!(ComputationalComplexity::Quadratic.to_string(), "O(n²)");
597        assert_eq!(MemoryComplexity::Linear.to_string(), "O(n)");
598    }
599
600    #[test]
601    fn test_method_documentation_available() {
602        assert!(get_method_documentation("linear").is_some());
603        assert!(get_method_documentation("cubic").is_some());
604        assert!(get_method_documentation("unknown").is_none());
605    }
606}
scirs2_interpolate/doc_enhancements.rs

scirs2_interpolate/
doc_enhancements.rs
