//
// A sparse array stores only non‑zero values.
// Scala's Map[Int, Int] is a natural fit:
// - Keys represent indices that actually exist
// - Values represent stored data
// - Lookup and insertion are fast
//
object SparseToDense {
// Sparse array type
type SparseArray = Map[Int, Int]
// Dense array type
type DenseArray = Vector[Int]
/*
buildDense:
Converts sparse → dense.
Steps:
1. Find the maximum index in the sparse structure
2. Allocate a dense vector of size maxIndex + 1
3. Fill with zeros
4. Copy sparse values into their positions
*/
def buildDense(sa: SparseArray): DenseArray = {
// Find largest index
val maxIndex: Int = if (sa.isEmpty) 0 else sa.keys.max
// Allocate dense vector filled with zeros
val dense: DenseArray = Vector.fill(maxIndex + 1)(0)
// Copy sparse values
dense.zipWithIndex.map { case (_, idx) =>
sa.getOrElse(idx, 0)
}
}
def main(args: Array[String]): Unit = {
// Sparse entries (zero values omitted)
val sa: SparseArray = Map(
2 -> 10,
10 -> 7,
8 -> 42,
3 -> 5
)
val dense: DenseArray = buildDense(sa)
println("Dense array:")
print("[ ")
dense.foreach(v => print(s"$v "))
println("]")
}
}
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
