Mega Code Archive
Sparse array implementation using TStringlist
<![CDATA[
Title: Sparse array implementation using TStringlist
Question: 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!}
]]>