Passing slice of a static/dynamic array by reference with start and length specifier
Asked Answered
L

3

13

Passing arrays (dynamic or static) to methods/procedures/functions with open array parameters, declaration can look like this:

procedure WorkWithArray( const anArray : array of Integer);
(* or procedure WorkWithArray( var anArray : array of Integer); *)
var
  i : Integer;
begin
  for i := Low(anArray) to High(anArray) do
  begin
    // Do something with the "open array" anArray
    WriteLn(anArray[i]);
  end;
end;

...
var
  staticArray : array[0..2] of Integer;
  dynArray : array of integer;
  dynArrayG : TArray<Integer>;
begin
  SetLength(dynArray,10);
  SetLength(dynArrayG,10);

  WorkWithArray(staticArray);  // Using a static array
  WorkWithArray(dynArray);     // Using a dynamic array
  WorkWithArray(dynArrayG);    // Using a dynamic generic array
  ...
end;

Passing arrays like this is a very common idiom used throughout the Delphi RTL, including some very optimized functions/procedures for handling arrays of data.


Suppose we need to call WorkWithArray with a subrange of our arrays. We can then use the intrinsic Slice() function.

First without an offset, starting with first index:

Type
  // Helper declarations
  TIntLongArray = array[0..MaxInt div SizeOf(Integer) - 1] of integer;
  PIntLongArray = ^TIntLongArray;

WorkWithArray(Slice(staticArray,2)); // No type cast needed for static arrays
WorkWithArray(Slice(PIntLongArray(@dynArray)^,2));
WorkWithArray(Slice(PIntLongArray(@dynArrayG)^,2));

Note: dynamic arrays does not fit directly into the Slice() function, see "Slice does not work with dynamic arrays". So the workaround method with type casting has to be used.


What if we want to work with a subrange not starting from the first element?

Doable as well:

WorkWithArray(Slice(PIntLongArray(@staticArray[1])^,2));
WorkWithArray(Slice(PIntLongArray(@dynArray[1])^,2));
WorkWithArray(Slice(PIntLongArray(@dynArrayG[1])^,2));

Note : the sum of the offset and the slice must not exceed the element count of the array.

I know that using Copy(myArray,x1,x2) could be used in cases where the input is declared as a const, but this will make a copy of the the array, and is ineffiecient for large arrays. (With risk of stack overflow as well).


Finally, my question:

While this demonstrates a way to pass a subrange of an array by reference with a start index and a length specifier, it looks a bit awkward. Are there better alternatives and if so how?

Lindbom answered 13/4, 2013 at 22:4 Comment(0)
L
9

Updated See a bit down for a generics solution.

Here is an alternative that encapsulates the type cast needed for the offset inside a function, which resides in an advanced record declared as a class function. Besides hiding the type cast, the offset is range checked against the high index of the array.

More types can be added if needed.

Type
  SubRange = record
    Type
      TIntLongArray = array[0..MaxInt div SizeOf(Integer) - 1] of integer;
      PIntLongArray = ^TIntLongArray;
      TByteLongArray = array[0..MaxInt div SizeOf(Byte) - 1] of Byte;
      PByteLongArray = ^TByteLongArray;

    class function Offset( const anArray : array of Integer; 
                                 offset  : Integer) : PIntLongArray; overload; static;
    class function Offset( const anArray : array of Byte; 
                                 offset  : Integer) : PByteLongArray; overload; static;
    // ToDo: Add more types ...
  end;

class function SubRange.Offset(const anArray : array of Integer; 
                                     offset  : Integer): PIntLongArray;
begin
  Assert(offset <= High(anArray));
  Result := PIntLongArray(@anArray[offset]);
end;

class function SubRange.Offset(const anArray : array of Byte; 
                                     offset  : Integer): PByteLongArray;
begin
  Assert(offset <= High(anArray));
  Result := PByteLongArray(@anArray[offset]);
end;

Note : the sum of the offset and the slice must not exceed the element count of the array.

Example calls:

WorkWithArray( Slice(SubRange.Offset(staticArray,1)^,2));
WorkWithArray( Slice(SubRange.Offset(dynArray,1)^,2));
WorkWithArray( Slice(SubRange.Offset(dynArrayG,1)^,2));

While this looks better, I'm still not convinced this is the optimal solution.


Update

When writing the above solution, I had a generics solution as the ultimate goal.

Here is an answer that utilizes anonymous methods and generics to implement a Slice(anArray,startIndex,Count) method that can be used with both static and dynamic arrays.

A straight generics solution would rely on range checking be turned off at every placed where it was used, and that would not be a pretty solution. The reason is that SizeOf(T) could not be used to declare a static array type of maximum size:

TGenericArray = array[0..MaxInt div SizeOf(T) - 1] of T; // SizeOf(T) not resolved

So we would have to use:

TGenericArray = array[0..0] of T;

instead. And this triggers the range check when it is on, for index > 0.

Solution

But the problem could be solved by another strategy, callbacks or a more modern terminology would be Inversion of Control (IoC) or Dependeny Injection (DI). The concept is best explained with, "Don't call me, we call you".

Instead of using a direct function, we pass the operational code as an anonymous method together with all parameters. Now the range check problem is contained within the Slice<T> frame.

Slice<Integer>.Execute(
  procedure(const arr: array of Integer)
  begin
    WriteLn(Math.SumInt(arr));
  end, dArr, 2, 7);

unit uGenericSlice;

interface

type
  Slice<T> = record
  private
    type
      PGenericArr = ^TGenericArr;
      TGenericArr = array [0..0] of T;
  public
    type
      TConstArrProc = reference to procedure(const anArr: array of T);
    class procedure Execute(       aProc: TConstArrProc;
                             const anArray: array of T;
                                   startIndex,Count: Integer); static;
  end;

implementation

class procedure Slice<T>.Execute(aProc: TConstArrProc;
  const anArray: array of T; startIndex, Count: Integer);
begin
  if (startIndex <= 0) then
    aProc(Slice(anArray, Count))
  else
  begin
    // The expression PGenericArr(@anArray[startIndex]) can trigger range check error
    {$IFOPT R+}
      {$DEFINE RestoreRangeCheck}
      {$R-}
    {$ENDIF}
    Assert((startIndex <= High(anArray)) and (Count <= High(anArray)-startIndex+1),
      'Range check error');
    aProc(Slice(PGenericArr(@anArray[startIndex])^, Count));
    {$IFDEF RestoreRangeCheck}
      {$UNDEF RestoreRangeCheck}
      {$R+}
    {$ENDIF}
  end;
end;

end.

Here are some example use cases:

program ProjectGenericSlice;

{$APPTYPE CONSOLE}

uses
  Math,
  uGenericSlice in 'uGenericSlice.pas';

function Sum(const anArr: array of Integer): Integer;
var
  i: Integer;
begin
  Result := 0;
  for i in anArr do
    Result := Result + i;
end;

procedure SumTest(const arr: array of integer);
begin
  WriteLn(Sum(arr));
end;

procedure TestAll;
var
  aProc: Slice<Integer>.TConstArrProc;
  dArr: TArray<Integer>;
  mySum: Integer;
const
  sArr: array [1 .. 10] of Integer = (
    1,2,3,4,5,6,7,8,9,10);

begin
  dArr := TArray<Integer>.Create(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

  aProc :=
    procedure(const arr: array of Integer)
    begin
      WriteLn(Sum(arr));
    end;

  // Test predefined anonymous method
  Slice<Integer>.Execute( aProc, dArr, 2, 7);

  // Test inlined anonymous method
  Slice<Integer>.Execute(
    procedure(const arr: array of Integer)
    begin
      WriteLn(Sum(arr));
    end, dArr, 2, 7);

  // Test call to Math.SumInt
  Slice<Integer>.Execute(
    procedure(const arr: array of Integer)
    begin
      WriteLn(Math.SumInt(arr));
    end, dArr, 2, 7);

  // Test static array with Low(sArr) > 0
  Slice<Integer>.Execute(
    procedure(const arr: array of Integer)
    begin
      WriteLn(Sum(arr));
    end, sArr, 3 - Low(sArr), 7);

  // Using a real procedure
  Slice<Integer>.Execute(
    SumTest, // Cannot be nested inside TestAll
    dArr, 2, 7);

  // Test call where result is passed to local var
  Slice<Integer>.Execute(
    procedure(const arr: array of Integer)
    begin
      mySum := Math.SumInt(arr);
    end, dArr, 2, 7);
  WriteLn(mySum);

end;

begin
  TestAll;
  ReadLn;
end.
Lindbom answered 13/4, 2013 at 22:4 Comment(11)
Why not simply reimplement Slice to accept dynamic arrays?Pya
@user3764855, Slice is a magic function (intrinsic) inserted by the compiler, not a normal function to overload or change per se.Lindbom
Can't you just return pointer to the array instead of using these anonymous methods.Pya
Yes, that is stated in the question, but I wanted a better way without a type cast.Lindbom
Can you post the solution with typecast? Thanks.Pya
@user3764855, see the question, it's all there. WorkWithArray(Slice(PIntLongArray(@dynArrayG[1])^,2));Lindbom
This is IMHO a much much cleaner approach pastebin.com/PGiFBKGs. Usage is simple. for I in TArrayManager<Integer>.SliceArray(A, 0, 7) do begin WriteLn(I); end;Pya
@user3764855, ok but you are copying the array elements. The whole idea behind the Slice is to avoid copying and work with the original data, only with a limited set.Lindbom
You can exchange pointers with ASM and there won't be no copy. I just don't think anonymous methods will be faster. Plus they are interface counted.Pya
@user3764855, imaging working with large arrays, setting up an anonymous frame is no big deal.Lindbom
Of course, the pastebin.com link is no longer valid, so you can't see the code user3764855 references. Which shows why we should post code in StackOverflow.Ligamentous
A
0

How about avoid open arrays and slice and use something like this ?

type
   TArrayRef<T> = record
   strict private
     type PointerOfT = ^T;
     FItems: PointerOfT;
     FCount: Integer;
   public  
     // FItems := @AItems[Offset]; FCount := Count;
     constructor Create(AItems: array of T; Offset, Count: Integer);
     property Items[Index: Integer]: T read GetItem; // Exit(FItems[Index])
     property Count: Integer read FCount; 
   end;
   TArrayRef = record // helpers
     class function Create<T>(AItems: array of T; Offset, Count: Integer); static;
     class function Create<T>(AItems: array of T; Count: Integer); static;
     class function Create<T>(AItems: array of T); static;
   end; 

procedure WorkWithArray(const anArray : TArrayRef<Integer>);
var
  I: Integer;
begin
  for I := 0 to anArray.Count - 1 do WriteLn(anArray[I]);
end;

WorkWithArray(TArrayRef.Create(StaticArray, 3)); // first three items
WorkWithArray(TArrayRef.Create(DynArray, 10, 3)); 
Asmara answered 18/1, 2015 at 19:22 Comment(0)
U
0

In case anyone else was tripped up like me. In older versions of Delphi (D2007 and older. Not sure about XE versions), you will also get E2193 errors if you use overloads:

  procedure Polygon(Points: array of TPoint); overload;
  procedure Polygon(Points: array of TDPoint); overload;

Works if remove overload:

  procedure Polygon(Points: array of TPoint); 
  procedure PolygonD(Points: array of TDPoint);

This is fixed in Delphi 10.3.0 (and probably other older versions too).

Unimpeachable answered 19/8, 2019 at 23:29 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.