use std::collections::HashMap;
/*
A sparse array stores only non‑zero values.
Rust's HashMap<usize, i32> is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
*/
type SparseArray = HashMap<usize, i32>;
type DenseArray = Vec<i32>;
/*
build_dense:
Converts sparse → dense.
Steps:
1. Find the maximum index in the sparse structure
2. Allocate a dense vector of size max_index + 1
3. Fill with zeros
4. Copy sparse values into their positions
*/
fn build_dense(sa: &SparseArray) -> DenseArray {
// Find largest index
let max_index: usize = sa.keys().copied().max().unwrap_or(0);
// Allocate dense vector filled with zeros
let mut dense: DenseArray = vec![0; max_index + 1];
// Copy sparse values
for (&index, &value) in sa.iter() {
dense[index] = value;
}
dense
}
fn main() {
// Sparse entries (zero values omitted)
let mut sa: SparseArray = SparseArray::new();
sa.insert(2, 10);
sa.insert(10, 7);
sa.insert(8, 42);
sa.insert(3, 5);
let dense: DenseArray = build_dense(&sa);
println!("Dense array:");
print!("[ ");
for v in dense.iter() {
print!("{} ", v);
}
println!("]");
}
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
