Question

How to build sparse array in Pascal

Answer 1

program SparseToDense;

{$mode delphi}{$H+}

{
    A small sparse array representation:
    - Each entry stores an index and a value
    - Zero values are simply not included
}

type
    TSparseEntry = record
        Index: SizeInt;
        Value: Integer;
    end;

    TSparseArray = array of TSparseEntry;

    TDenseArray = array of Integer;   { <-- Named return type fixes the error }

{
    buildDense:
    Converts sparse entries into a dense array.

    Steps:
    1. Find the largest index
    2. Allocate an array of size maxIndex + 1
    3. Fill with zeros
    4. Copy sparse values into their positions
}
function buildDense(const SA: TSparseArray): TDenseArray;
var
    i: SizeInt;
    maxIndex: SizeInt;
begin
    maxIndex := 0;

    { Find largest index }
    for i := 0 to High(SA) do
        if SA[i].Index > maxIndex then
            maxIndex := SA[i].Index;

    { Allocate dense array filled with zeros }
    SetLength(Result, maxIndex + 1);

    { Copy sparse values }
    for i := 0 to High(SA) do
        Result[SA[i].Index] := SA[i].Value;
end;

var
    SA: TSparseArray;
    Dense: TDenseArray;
    i: Integer;

begin
    { Sparse entries (zero values omitted) }
    SetLength(SA, 4);
    SA[0].Index := 2;  SA[0].Value := 10;
    SA[1].Index := 10; SA[1].Value := 7;
    SA[2].Index := 8;  SA[2].Value := 42;
    SA[3].Index := 3;  SA[3].Value := 5;

    Dense := buildDense(SA);

    WriteLn('Dense array:');
    Write('[ ');
    for i := 0 to High(Dense) do
        Write(Dense[i], ' ');
    WriteLn(']');
end.



{
run:

Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]

}

 

70+ SQL courses for beginners and professionals

Answer 2

program SparseToDense;

{
    A sparse array stores only non‑zero values.
    TDictionary<SizeInt, Integer> is a natural fit:
      - Keys represent indices that actually exist
      - Values represent stored data
      - Lookup and insertion are fast
}

{$mode objfpc}{$H+}

uses
    SysUtils, Generics.Collections;

type
    TSparseArray = specialize TDictionary<SizeInt, Integer>;
    TDenseArray  = array of Integer;

{
    buildDense:
    Converts sparse → dense.

    Steps:
    1. Find the maximum index in the sparse structure
    2. Allocate a dense array of size maxIndex + 1
    3. Fill with zeros (SetLength does this automatically)
    4. Copy sparse values into their positions
}
function buildDense(const SA: TSparseArray): TDenseArray;
var
    maxIndex: SizeInt;
    key: SizeInt;
begin
    maxIndex := 0;

    { Find largest index }
    for key in SA.Keys do
        if key > maxIndex then
            maxIndex := key;

    { Allocate dense array }
    SetLength(Result, maxIndex + 1);

    { Copy sparse values }
    for key in SA.Keys do
        Result[key] := SA.Items[key];
end;

var
    SA: TSparseArray;
    Dense: TDenseArray;
    key: SizeInt;

begin
    SA := TSparseArray.Create;

    try
        { Sparse entries (zero values omitted) }
        SA.Add(2, 10);
        SA.Add(10, 7);
        SA.Add(8, 42);
        SA.Add(3, 5);

        Dense := buildDense(SA);

        WriteLn('Dense array:');
        Write('[ ');
        for key := 0 to High(Dense) do
            Write(Dense[key], ' ');
        WriteLn(']');
    finally
        SA.Free;
    end;
end.



{
run:

Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]

}

 

70+ SQL courses for beginners and professionals