Deleting elements from a dynamic array

In my blog "Initialising Dynamic Arrays" I mentioned I have been writing some unit tests that needed numerous repetative array initialisation operations. Well, one of the other common operations I found myself writing was the deletion of items from dynamic arrays. So I decided to find a generic way of doing this.

Assuming we know the index of the item to be deleted we need the equivalent of Delphi's built-in Delete procedure for strings. If you read the previous post you won't be surprised to learn that I decided to further extend the Generics.Collections.TArray class by adding to the TArrayEx class I introduced there.

My first attempt emulates Delphi's Delete procedure by deleting the array element in-place: i.e. it updates the array passed as a parameter. Unsurprisingly the method is called DeleteInPlace. Here's how it goes:

type
  TArrayEx = class(TArray)
  public
    ...
    class procedure DeleteInPlace<T>(var A: TArray<T>; const Index: Integer);
  end;

...

class procedure TArrayEx.DeleteInPlace<T>(var A: TArray<T>;
  const Index: Integer);
var
  IdxA: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  for IdxA := Index to Pred(High(A)) do
    A[IdxA] := A[Succ(IdxA)];
  SetLength(A, Length(A) - 1);
end;

This uses a common algorithm. It just copies all array elements above the index of the deleted item down one place then shrinks the array by one element.

Next I decided it would also be useful to be able to construct a new array that contained a copy of a given array with the specified element removed. Continuing my startlingly inspired naming plan I called this method Delete. Here it is:

type
  TArrayEx = class(TArray)
  public
    ...
    class function Delete<T>(const A: array of T; const Index: Integer):
      TArray<T>;
  end;

...

class function TArrayEx.Delete<T>(const A: array of T; const Index: Integer):
  TArray<T>;
var
  IdxSrc, IdxRes: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  SetLength(Result, Length(A) - 1);
  IdxRes := Low(Result);
  for IdxSrc := Low(A) to High(A) do
  begin
    if IdxSrc <> Index then
    begin
      Result[IdxRes] := A[IdxSrc];
      Inc(IdxRes);
    end;
  end;
end;

This is pretty self-explanatory. It simply creates a new array of the required size and copies all the array elements to it, except for the one that is to be deleted.

I could have implemented Delete in terms of DeleteIinPlace like this, using CloneArray from the previous post:

class function TArrayEx.Delete<T>(const A: array of T; const Index: Integer):
  TArray<T>;
var
  IdxSrc, IdxRes: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  Result := CloneArray<T>(A);
  DeleteInPlace<T>(Result, Index);
end;

But I decided against this to avoid looping through the array 1.5 times on average instead of once. (CloneArray loops through the array once and DeleteInPlace loops through half the array on average.)

OK, I'll come clean. I actually wrote Delete first and then DeleteInPlace after I found the compiler wouldn't accept it as an overload of Delete, but the story goes better the way I told it!

Does anyone know why the compiler won't accept that methods with different return types (or no return types) have different signatures anyway? Leave a comment if you know please.

Source code highlighting by DelphiDabbler PasHi.