Sparse array implementation using TStringlist (Views: 30)
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! |