Sparse array implementation using TStringlist

Problem/Question/Abstract:

Sparse arrays are arrays that only uses memory for the cells that are actually in use although the full size of the array is always available. A prime example is the cells in a spreadsheet application: they can have enormous dimensions (like 99999 * 99999 cells) but still only use memory equivalent to the cells where there is any data. This article shows how you can easily create a sparse array with any number of dimensions and of arbitrary size.

Answer:

One solution is to create a new class (let's call it TSparseArray) that stores the data in a TStringlists Objects array and the dimensions in the Strings array as a compound string. Here's a two-dimensional example:

interface

type
  TSparseArray = class(TObject)
  private
    FCells: TStringlist;
    function GetCell(Col, Row: integer): TObject;
    procedure SetCell(Col, Row: integer; const Value: TObject);
  public
    constructor Create;
    destructor Destroy; override;
    property Cells[Col, Row: integer]: TObject read GetCell write SetCell; default;
  end;

implementation

const
  cFmtDims = '%d:%d';

constructor TSparseArray.Create;
begin
  inherited Create;
  FCells := TStringlist.Create;
  FCells.Sorted := true; // faster retrieval, slower updates, needed for dupIgnore
  FCells.Duplicates := dupIgnore;
end;

destructor TSparseArray.Destroy;
begin
  FCells.Free;
  inherited Destroy;
end;

function TSparseArray.GetCell(Col, Row: integer): TObject;
var
  i: integer;
begin
  Result := nil;

  i := FCells.IndexOf(Format(cFmtDims, [Col, Row]));
  if i > -1 then
    Result := FCells.Objects[i];
end;

procedure TSparseArray.SetCell(Col, Row: integer; const Value: TObject);
begin
  // dupIgnore guarantees that if this cell already exists, this will overwrite it
  FCells.AddObject(Format(cFmtDims, [Col, Row]), Value);
end;

end.

To create a sparse array with more dimensions, you just have to redefine the Cells property (and the read / write methods) and change the format of cFmtDims accordingly. You can even mix dimensions of different types (i.e Cells[const Row:string;Col:integer]:TObject). I think you can come up with more neat things yourself. Enjoy!