Skip to main content

fastcit_core/
dataset.rs

1//! Data-bound container shared by every conditional-independence test.
2//!
3//! A [`Dataset`] is built once from named columns. Discrete columns are
4//! *factorized* up front into contiguous integer codes (`0..cardinality`) so
5//! the discrete tests can operate on cheap `usize` codes instead of repeatedly
6//! hashing floats. Continuous columns keep their raw `f64` values.
7//! NaN values are rejected at construction ([`CIError::MissingData`]); choose
8//! and apply a missing-data convention (drop / impute) before binding.
9
10use std::collections::HashMap;
11use std::sync::{Arc, OnceLock};
12
13use crate::error::CIError;
14use crate::gram::GramCache;
15use crate::strata::{StrataCache, StrataPartition};
16
17/// Whether a column holds categorical (discrete) or numeric (continuous) data.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum ColumnKind {
20    /// Categorical data; values are factorized into integer codes.
21    Discrete,
22    /// Numeric data; values are kept as `f64`.
23    Continuous,
24}
25
26/// Stored representation of a single column.
27#[derive(Debug, Clone)]
28pub(crate) enum Column {
29    /// Factorized discrete column: per-row codes plus the number of distinct
30    /// categories.
31    Discrete {
32        codes: Vec<usize>,
33        cardinality: usize,
34    },
35    /// Raw continuous column.
36    Continuous { values: Vec<f64> },
37}
38
39/// A named, typed, immutable table of columns.
40///
41/// Build one with [`Dataset::from_columns`]; tests then refer to columns by
42/// their integer index (see [`Dataset::index_of`]).
43#[derive(Debug)]
44pub struct Dataset {
45    names: Vec<String>,
46    name_to_index: HashMap<String, usize>,
47    columns: Vec<Column>,
48    n_rows: usize,
49    /// Lazily built Gaussian sufficient-statistic cache (means + centered
50    /// cross-product matrix). Populated on first access via [`Dataset::gram`].
51    gram: OnceLock<Option<GramCache>>,
52    /// Lazily built, budget-bounded cache of stratum partitions keyed by the
53    /// sorted conditioning-set indices (see [`Dataset::strata_partition`]).
54    strata_cache: StrataCache,
55}
56
57/// Canonicalize a float for factorization so that `-0.0` and `0.0` share a
58/// code. NaN never reaches this function: `from_columns` rejects NaN columns
59/// up front (strict missing-data policy).
60fn canonical_bits(v: f64) -> u64 {
61    if v == 0.0 {
62        // Collapse -0.0 and 0.0.
63        0.0_f64.to_bits()
64    } else {
65        v.to_bits()
66    }
67}
68
69impl Dataset {
70    /// Build a dataset from `(name, kind, values)` triples.
71    ///
72    /// Discrete columns are factorized into contiguous codes (`0..cardinality`)
73    /// in first-seen order; `-0.0`/`0.0` are grouped together.
74    /// Continuous columns store their raw values.
75    ///
76    /// # Errors
77    ///
78    /// Returns [`CIError::DimensionMismatch`] if the columns do not all share a
79    /// common length, or if two columns share a name (names must be unique).
80    /// Returns [`CIError::MissingData`] if a discrete column contains NaN, or a
81    /// continuous column contains any non-finite value (NaN or ±inf).
82    pub fn from_columns(cols: Vec<(String, ColumnKind, Vec<f64>)>) -> Result<Self, CIError> {
83        let n_rows = cols.first().map_or(0, |(_, _, v)| v.len());
84        for (name, _, values) in &cols {
85            if values.len() != n_rows {
86                return Err(CIError::DimensionMismatch(format!(
87                    "column `{name}` has length {} but expected {n_rows}",
88                    values.len(),
89                )));
90            }
91        }
92
93        let mut names = Vec::with_capacity(cols.len());
94        let mut name_to_index = HashMap::with_capacity(cols.len());
95        let mut columns = Vec::with_capacity(cols.len());
96
97        for (idx, (name, kind, values)) in cols.into_iter().enumerate() {
98            // Discrete columns reject NaN (missing); continuous columns reject any
99            // non-finite value (NaN or ±inf), which would corrupt the Gram path.
100            let bad = match kind {
101                ColumnKind::Continuous => values.iter().position(|v| !v.is_finite()),
102                ColumnKind::Discrete => values.iter().position(|v| v.is_nan()),
103            };
104            if let Some(row) = bad {
105                return Err(CIError::MissingData(format!(
106                    "column `{name}` contains NaN/missing values (first at row {row}); \
107                     remove or impute before building the Dataset"
108                )));
109            }
110            let column = match kind {
111                ColumnKind::Continuous => Column::Continuous { values },
112                ColumnKind::Discrete => {
113                    let mut lookup: HashMap<u64, usize> = HashMap::new();
114                    let mut codes = Vec::with_capacity(values.len());
115                    for v in values {
116                        let key = canonical_bits(v);
117                        let next = lookup.len();
118                        let code = *lookup.entry(key).or_insert(next);
119                        codes.push(code);
120                    }
121                    Column::Discrete {
122                        cardinality: lookup.len(),
123                        codes,
124                    }
125                }
126            };
127            if name_to_index.insert(name.clone(), idx).is_some() {
128                return Err(CIError::DimensionMismatch(format!(
129                    "duplicate column name `{name}`; column names must be unique"
130                )));
131            }
132            names.push(name);
133            columns.push(column);
134        }
135
136        Ok(Self {
137            names,
138            name_to_index,
139            columns,
140            n_rows,
141            gram: OnceLock::new(),
142            strata_cache: StrataCache::default(),
143        })
144    }
145
146    /// Number of rows (observations).
147    #[must_use]
148    pub fn n_rows(&self) -> usize {
149        self.n_rows
150    }
151
152    /// Number of columns.
153    #[must_use]
154    pub fn n_cols(&self) -> usize {
155        self.columns.len()
156    }
157
158    /// Name of the column at `index`, if any.
159    #[must_use]
160    pub fn name_of(&self, index: usize) -> Option<&str> {
161        self.names.get(index).map(String::as_str)
162    }
163
164    /// Index of the column named `name`, if present.
165    #[must_use]
166    pub fn index_of(&self, name: &str) -> Option<usize> {
167        self.name_to_index.get(name).copied()
168    }
169
170    /// Read a discrete column as `(codes, cardinality)`.
171    ///
172    /// # Errors
173    ///
174    /// Returns [`CIError::UnknownColumn`] if `index` is out of range, or
175    /// [`CIError::WrongColumnKind`] if the column is continuous.
176    /// Borrow the column at `index`, mapping an out-of-range index to
177    /// [`CIError::UnknownColumn`].
178    fn column(&self, index: usize) -> Result<&Column, CIError> {
179        self.columns
180            .get(index)
181            .ok_or_else(|| CIError::UnknownColumn(format!("column index {index}")))
182    }
183
184    pub(crate) fn discrete(&self, index: usize) -> Result<(&[usize], usize), CIError> {
185        match self.column(index)? {
186            Column::Discrete { codes, cardinality } => Ok((codes, *cardinality)),
187            Column::Continuous { .. } => Err(CIError::WrongColumnKind(format!(
188                "column {index} is continuous but a discrete column was required"
189            ))),
190        }
191    }
192
193    /// Read a continuous column's values.
194    ///
195    /// # Errors
196    ///
197    /// Returns [`CIError::UnknownColumn`] if `index` is out of range, or
198    /// [`CIError::WrongColumnKind`] if the column is discrete.
199    pub(crate) fn continuous(&self, index: usize) -> Result<&[f64], CIError> {
200        match self.column(index)? {
201            Column::Continuous { values } => Ok(values),
202            Column::Discrete { .. } => Err(CIError::WrongColumnKind(format!(
203                "column {index} is discrete but a continuous column was required"
204            ))),
205        }
206    }
207
208    /// The lazily built Gaussian sufficient-statistic cache, or `None` when
209    /// the dataset has no continuous columns / too many of them (see
210    /// [`crate::gram::MAX_GRAM_COLS`]).
211    ///
212    /// `OnceLock::get_or_init` runs the build exactly once, blocking any
213    /// concurrent callers until it completes; the stored cache is therefore
214    /// built a single time and is deterministic.
215    pub(crate) fn gram(&self) -> Option<&GramCache> {
216        self.gram.get_or_init(|| GramCache::build(self)).as_ref()
217    }
218
219    /// The stratum partition for conditioning set `z`, cached per distinct
220    /// (order-insensitive) set of column indices. On a miss the partition is
221    /// built outside the lock and inserted only while the total cache stays
222    /// within the cache's byte budget; once the budget is reached, further
223    /// sets are computed per call without caching.
224    ///
225    /// # Errors
226    ///
227    /// Returns the usual column errors ([`CIError::WrongColumnKind`] /
228    /// [`CIError::UnknownColumn`]) if any `z` column is not discrete.
229    pub(crate) fn strata_partition(&self, z: &[usize]) -> Result<Arc<StrataPartition>, CIError> {
230        self.strata_cache.get_or_build(self, z)
231    }
232}
233
234impl Clone for Dataset {
235    /// Clones the column data; the lazy caches (Gram matrix, stratum
236    /// partitions) start fresh in the clone and are rebuilt on demand.
237    fn clone(&self) -> Self {
238        Self {
239            names: self.names.clone(),
240            name_to_index: self.name_to_index.clone(),
241            columns: self.columns.clone(),
242            n_rows: self.n_rows,
243            gram: OnceLock::new(),
244            strata_cache: StrataCache::default(),
245        }
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    #[test]
254    fn factorizes_discrete_first_seen() {
255        let ds = Dataset::from_columns(vec![(
256            "a".to_string(),
257            ColumnKind::Discrete,
258            vec![5.0, 5.0, 2.0, 2.0, 5.0],
259        )])
260        .unwrap();
261        let (codes, card) = ds.discrete(0).unwrap();
262        assert_eq!(card, 2);
263        assert_eq!(codes, &[0, 0, 1, 1, 0]);
264        assert_eq!(ds.n_rows(), 5);
265    }
266
267    #[test]
268    fn groups_neg_zero() {
269        let ds = Dataset::from_columns(vec![(
270            "a".to_string(),
271            ColumnKind::Discrete,
272            vec![0.0, -0.0, 1.0],
273        )])
274        .unwrap();
275        let (codes, card) = ds.discrete(0).unwrap();
276        // 0.0 and -0.0 share a code; 1.0 is its own.
277        assert_eq!(card, 2);
278        assert_eq!(codes, &[0, 0, 1]);
279    }
280
281    #[test]
282    fn nan_errors_in_any_column_kind() {
283        for kind in [ColumnKind::Discrete, ColumnKind::Continuous] {
284            let err =
285                Dataset::from_columns(vec![("a".to_string(), kind, vec![1.0, f64::NAN, 2.0])])
286                    .unwrap_err();
287            assert!(
288                matches!(err, CIError::MissingData(_)),
289                "kind {kind:?}: {err}"
290            );
291            let msg = err.to_string();
292            assert!(msg.contains("`a`"), "message should name the column: {msg}");
293            assert!(msg.contains("row 1"), "message should give the row: {msg}");
294        }
295    }
296
297    #[test]
298    fn duplicate_column_names_error() {
299        let err = Dataset::from_columns(vec![
300            ("a".to_string(), ColumnKind::Continuous, vec![1.0, 2.0]),
301            ("a".to_string(), ColumnKind::Continuous, vec![3.0, 4.0]),
302        ])
303        .unwrap_err();
304        assert!(matches!(err, CIError::DimensionMismatch(_)), "{err}");
305        assert!(err.to_string().contains("`a`"));
306    }
307
308    #[test]
309    fn infinite_continuous_value_errors() {
310        let err = Dataset::from_columns(vec![(
311            "a".to_string(),
312            ColumnKind::Continuous,
313            vec![1.0, f64::INFINITY, 2.0],
314        )])
315        .unwrap_err();
316        assert!(matches!(err, CIError::MissingData(_)), "{err}");
317        assert!(err.to_string().contains("row 1"));
318    }
319
320    #[test]
321    fn continuous_round_trips() {
322        let ds = Dataset::from_columns(vec![(
323            "x".to_string(),
324            ColumnKind::Continuous,
325            vec![1.5, 2.5, 3.5],
326        )])
327        .unwrap();
328        assert_eq!(ds.continuous(0).unwrap(), &[1.5, 2.5, 3.5]);
329        assert_eq!(ds.index_of("x"), Some(0));
330        assert_eq!(ds.index_of("nope"), None);
331    }
332
333    #[test]
334    fn mismatched_lengths_error() {
335        let err = Dataset::from_columns(vec![
336            ("a".to_string(), ColumnKind::Continuous, vec![1.0, 2.0]),
337            ("b".to_string(), ColumnKind::Continuous, vec![1.0]),
338        ])
339        .unwrap_err();
340        assert!(matches!(err, CIError::DimensionMismatch(_)));
341    }
342
343    #[test]
344    fn wrong_kind_errors() {
345        let ds = Dataset::from_columns(vec![(
346            "a".to_string(),
347            ColumnKind::Discrete,
348            vec![1.0, 2.0],
349        )])
350        .unwrap();
351        assert!(matches!(ds.continuous(0), Err(CIError::WrongColumnKind(_))));
352        assert!(matches!(ds.discrete(9), Err(CIError::UnknownColumn(_))));
353    }
354
355    #[test]
356    fn clone_starts_with_fresh_caches() {
357        let ds = Dataset::from_columns(vec![
358            ("x".into(), ColumnKind::Discrete, vec![1., 2., 1., 2.]),
359            ("z".into(), ColumnKind::Discrete, vec![1., 1., 2., 2.]),
360        ])
361        .unwrap();
362        let before = ds.strata_partition(&[1]).unwrap();
363        let cloned = ds.clone();
364        let after = cloned.strata_partition(&[1]).unwrap();
365        // Same content, but the clone rebuilt its own partition.
366        assert_eq!(before.starts, after.starts);
367        assert_eq!(before.rows, after.rows);
368        assert!(!std::sync::Arc::ptr_eq(&before, &after));
369    }
370}