arraysdelphimultidimensional-arraylazarustlist

Delphi dynamic array with tlist


I'm creating a simple interpreter in Delphi/Lazarus for a language similar to BASIC. I already achieved a lot of functionalities. At this moment, I'm trying to create a DIM like command in order to handle multidimensional numeric arrays. My idea is to use TList to simulate multidimensional arrays limited only by available memory. For example, when a declare in my interpreter a command like the following:

DIM num_arr[3,3,3]

I would like to create a three dimensional array of double, with each index varying from 0 to 2.

So far I have only the function to create the "TList array". I'm using two TList objects to keep the array dimensions and the data items list, I have a third one that holds the indexes for store/retrieve data. What I can't figure is how to associate a list of indexes to a specific entry in the TList. It's simple when the array is up to two dimensions, I can convert each pair of indexes to a numeric sequence, but no success to three and more dimensions. Is there any algorithm I could use to solve that? It's really hard to find something related to that matter. Any suggestion about how to implement something similar is welcome. Below I'm publishing part of the code I developed so far:

//Creates a "n" dimensional array
function array_allocate(Dim: TList; var DataArray: TList): integer;
var
  i: integer;
  s: string;
begin
  Result := 1;
  //Simple way to find the array length
  //For example. An array with dimensions [3,3,3] will handle 27 items
  for i := 0 to Dim.Count-1 do
  begin
    Result := Result * Integer(Dim[i]);
  end;
  Result := Result;
  DataArray.Capacity := Result; //DataArray now handles 27 items

  //************************************
  //Every line below is just for testing
  //************************************
  fmMain.Memo1.Lines.Add('Allocating size for array with '+IntToStr(Dim.Count)+' dimension(s).');
  s := '';
  for i := 0 to Dim.Count-1 do
    s := s + '['+IntToStr(Integer(Dim[i]))+']';
  fmMain.Memo1.Lines.Add('DIM Sizes: '+s);
  fmMain.Memo1.Lines.Add('Manage: '+IntToStr(Result)+' Items.');
end;

{*************************************}
{NOT functional, this is the challenge}
{*************************************}
function calculate_offset(Dim, Indexes: TList; var DataArray: TList; BaseAddr: integer): integer;
var
  i, Depth, dimIdx: Integer;
  k,index,sizeProduct: integer;
begin
  for Depth := 0 to Dim.Count-1 do
    for dimIdx := 0 to Integer(Dim[Depth])-1 do
      fmMain.mmOut.Lines.Add('Dim: '+IntToStr(Depth)+' ,Index: '+IntToStr(dimIdx));

  result := 0;
end;

procedure TfmMain.FormShow(Sender: TObject);
var
  dataList: TList; //keep the data
  dimList: TList; //keep the dimensions
  indexList: TList; //keep the indexes
  offset: integer;
begin
  dimList := TList.Create; //create the dim array
  //simulate the creation of an array with dimension [3,3,3]
  //something like DIM myVar[3,3,3]
  dimList.Add(Pointer(3));
  dimList.Add(Pointer(3));
  dimList.Add(Pointer(3));

  dataList := TList.Create; //create the data list
  array_allocate(dimList, dataList); //allocates memory

  //indexList is the way to indicate which index to retrieve/store data
  indexList := TList.Create;
  indexList.Add(Pointer(1));
  indexList.Add(Pointer(1));
  indexList.Add(Pointer(1));
  indexList.Add(Pointer(1));

  //The idea is to relate indexes like [0,0,0], [0,0,1], [0,1,1] to
  //a numeric sequence between 0 to 26 in this case (DIM = [3,3,3])
  offset := calculate_offset(dimList, indexList, dataList, 1, 0);

  indexList.Free;
  dimList.Free;
  dataList.Free;
end;

Solution

  • As I read your question, you want to convert from a tuple of indices to a linear index, assuming row major storage.

    Suppose the dimensions are held in a dynamic array, dim and the indices are in a dynamic array, idx. Then the linear index is calculated like this:

    function LinearIndex(const dim, idx: array of Integer): Integer;
    var 
      i: Integer;
    begin
      Assert(Length(dim)=Length(idx));
      Assert(Length(dim)>0);
      Result := idx[0];
      for i := 1 to high(dim) do
        Result := Result*dim[i-1] + idx[i];
    end;