1
votes

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;
2
I'm sceptical of your chosen data structure. I think you want a data type to hold the dimensions, and a flat array for the content. I'd make it a dynamic array of the element type. The dimensions would be held in TArray<Integer>. The length of the dynamic array is the product of the dimensions.David Heffernan
If it is meant to be flexible, a higher level approach may be more suitable. One option might be a TNDimPoint class that would hold, at least, an integer for the number of dimensions and a TList<integer> for coordinate entries for each dimension. The data could then be held in a class like TNDimArray<T> = class(TObjectDictionary<TNDimPoint, T>) (with dictionary owns keys) with suitable comparers written for TNDimPoint - this would guarantee uniqueness of entries, give you fast random access to the data, and be virtually unlimited in the size or dimension of the problem.J...
The above approach would be particularly useful for (irregular, non-symmetric, etc) sparse matrices, for example, where you would only need to store the data that is defined rather than need to allocate the entirety of the array if only a small number of points will be occupied. It really depends on what the end goal is.J...
Ask yourself what you think Result := Result does. You are also missing try/finally for lifetime management. Surely you aren't building an interpreter mixed in with your GUI. Surely TLIST isn't the best choice of container. Even if you are stuck on pre-generics Delphi you can make some type safe containers to avoid those tedious and error prone casts.David Heffernan
Hi J..., that's a very nice approach. Thanks.André Murta

2 Answers

3
votes

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;
0
votes

The LinearIndex function described above was not functional to certain unbalanced arrays. For example, if I properly allocate "dim" to hold the value [2,3], the function would return 2 as the index for both contents of "idx": [0,2], [1,0]. I created a Pascal function based on another post I found here at StackOverflow and this one seems to work.

function LinearIndex2(const dim, idx: array of Integer): Integer;
var
  i,index,mult: Integer;
begin
  Assert(Length(dim)=Length(idx));
  Assert(Length(dim)>0);

  index := 0; mult := 1;
  for i := 0 to High(dim) do
  begin
    index := index + idx[i] * mult;
    mult := mult * dim[i];
  end;

  result := index;
end;